package Demo18;

import java.util.Arrays;

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 */
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[] {-1,-1};
        // 这里是处理边界问题
        if(nums.length == 0) {
            return ret;
        }
        // 查找区间的左端点
        int left = 0,right = nums.length - 1;
        while(left < right) { // 这里是不可以等于的,如果等于了就会死循环
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        // 判断返回值是否存在
        if(nums[left] != target) return ret; // target 不存在,直接返回 -1 , -1
        ret[0] = left;// 否则修改返回值的下标
        // 查找区间的右端点
        // 此处有个小细节, 就是 left 可以不修改,因为left 是指向 的区间的左端点,是有效的位置,可以只修改右端点,因为有端点只会在左端点和做端点的右边
        left = 0; right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) {
                right = mid - 1;
            }else {
                left = mid;
            }
        }
        ret[1] = right;
        return ret;
    }
    public int[] searchRange1(int[] nums, int target) {
        int begin = -1,end = -1;
        int left = 0,right = nums.length - 1;
        if(right < 0) {
            return new int[] {-1,-1};
        }
        // 求左区间端点
        while(left < right) {
            int min = left + (right - left) / 2;
            if(nums[min] < target) {
                left = min + 1;
            }else {
                // nums[min] >= target
                right = min;
            }
            if(nums[min] == target) {
                begin = left;
            }
        }
        if(nums[left] == target) begin = left;
        // 求右区间端点
        left = 0;right = nums.length - 1;
        while(left < right) {
            int min = left + (right - left + 1) / 2;
            if(nums[min] <= target) {
                left = min;
            }else {
                // nums[min] > target
                right = min - 1;
            }
            if(nums[min] == target) {
                end = left;
            }
        }
        if(nums[right] == target) end = right;
        return new int[] {begin,end};
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] ret = solution.searchRange(new int[] {1} , 1);
        System.out.println(Arrays.toString(ret));
    }
}